#include "DoubleLinkList.h"

DoubleLinkList::DoubleLinkList()
{
    size = 0;
    head = tail = new Node(0);
    Free = nullptr;
    CopyData = nullptr;   //
    Compare = nullptr;
    Greater = nullptr;
    Print = nullptr;
}

DoubleLinkList::DoubleLinkList(const DoubleLinkList &list)
{
    size = list.size;
    head = new Node(0); 
    Node * tp = head;
    Node * travelPoint = list.head->next;

    CopyData = list.CopyData;   //
    Free = list.Free;
    Compare = list.Compare;
    Greater = list.Greater;
    Print = list.Print;

    while(travelPoint != nullptr)
    {
        Node * newNode = new Node(travelPoint->value);
        tp->next = newNode;
        newNode->prev = tp;
        tp = tp->next;
        travelPoint = travelPoint->next;
        if(Free != nullptr)         //
            newNode->value = CopyData(newNode->value);      //
    }
    tail = tp;
     
}

DoubleLinkList &DoubleLinkList::operator=(const DoubleLinkList &list)
{
    while (head != nullptr)
    {
        Node * nextNode = head->next;
        delete head;
        head = nextNode;
    }
    tail = nullptr;

    size = list.size;
    head = new Node(0);
    Node *tp = head;
    Node *travelPoint = list.head->next;
    CopyData = list.CopyData;   //
    Free = list.Free;
    Compare = list.Compare;
    Greater = list.Greater;
    Print = list.Print;
    while(travelPoint != nullptr)
    {
        Node *newNode = new Node(travelPoint->value);
        tp->next = newNode;
        newNode->prev = tp;
        tp = tp->next;
        travelPoint = travelPoint->next;
        if(Free != nullptr)         //
            newNode->value = CopyData(newNode->value); 
    }
    tail = tp;
  
    return *this;
}

DoubleLinkList::~DoubleLinkList()
{
    if(Free)
    {
        Node * travelPoint = head->next;
        while(travelPoint != nullptr)
        {
            Free(travelPoint->value);
            travelPoint = travelPoint->next;
        }
    }
    while(head != nullptr)
    {
        Node *nextNode = head->next;
        delete  head;
        head = nextNode;
    }
    tail = nullptr;    
}

void DoubleLinkList::InsertTail(const ElementType &element)     //O(1)
{
    Node *newNode = new Node(element);
    tail->next = newNode;
    newNode->prev = tail;
    tail = newNode;
    size++;

    if(Free != nullptr)
        newNode->value = CopyData(newNode->value);
}

void DoubleLinkList::InsertByIndex(size_t index, const ElementType &element)    //O(n)
{
    if(index > size)
    {
        std::cout << "位置非法\n";
        return ;
    }
    Node * travelPoint = head;
    for(size_t i = 0; i < index; i++)//尽量不要对size_t做减法
    {
        travelPoint = travelPoint->next;
    }
    Node *newNode = new Node(element);
    newNode->next = travelPoint->next;
    newNode->prev = travelPoint;

    travelPoint->next = newNode;
    if(size != 0)
        newNode->next->prev = newNode;
    size++;

    if(Free != nullptr)
        newNode->value = CopyData(newNode->value);  
}

void DoubleLinkList::RemoveByIndex(size_t index)
{
    if(index >= size)
    {
        std::cout << "删除位置不存在\n";
        return ;
    }
    Node * travelPoint = head->next;
    for(size_t i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    travelPoint->prev->next = travelPoint->next;
    if(travelPoint->next != nullptr)
        travelPoint->next->prev = travelPoint->prev;
    else
        tail = travelPoint->prev;

    if(Free != nullptr)
        Free(travelPoint->value);
    delete travelPoint;
    size--;
}

void DoubleLinkList::RemoveByElement(const ElementType &element)
{
    Node *travelPoint = head;
    while(travelPoint->next != nullptr)
    {
        if(Compare(travelPoint->next->value,element))   //travelPoint->value == element
        {
            Node * freeNode = travelPoint->next;
            freeNode->prev->next = freeNode->next;
            if(freeNode->next != nullptr)
                freeNode->next->prev = freeNode->prev;
            else
                tail = freeNode->prev;
            
            if(Free != nullptr)
                Free(freeNode->value);
            delete freeNode;
            size--;
        }
        else
        {
            travelPoint = travelPoint->next;
        }
    }
}

DoubleLinkList::ElementType *DoubleLinkList::FindByIndex(size_t index)
{
    if(index >= size)
        return nullptr;
    Node * travelPonit = head->next;
    for(size_t i = 0; i < index; i++)
    {
        travelPonit = travelPonit->next;
    }
    return &travelPonit->value;
}

// DARRAY::DynamicArray DoubleLinkList::FindeByElement(const ElementType &element)
// {
//     DARRAY::DynamicArray result;
//     Node * travelPoint = head->next;
//     while(travelPoint != nullptr)
//     {
//         if(Compare(travelPoint->value,element))   //travelPoint->value == element
//             result.InsertTail(travelPoint->value);
//         travelPoint = travelPoint->next;
//     }
//     return result;
// }

void DoubleLinkList::UpdataByIndex(size_t index, const ElementType &element)
{
    if(index >= size)
    {
        std::cout <<"位置非法\n";
        return ;
    }
    Node * travelPoint = head->next;
    for(size_t i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    if(Free != nullptr)
        Free(travelPoint->value);
    if(Free == nullptr)
        travelPoint->value = element;
    else
        travelPoint->value = CopyData(element);
}

void DoubleLinkList::UpdataByElement(const ElementType &oldValue, const ElementType &newValue)
{
    Node * travelPoint = head->next;
    while(travelPoint != nullptr)
    {
        if(Compare(travelPoint->value,oldValue))      //travelPoint->value == oldValue
        {
            if(Free != nullptr)
                Free(travelPoint->value);
            if(Free == nullptr)
                travelPoint->value = newValue;
            else
                travelPoint->value = CopyData(newValue);
        }
        travelPoint = travelPoint->next;
    }        
}

void DoubleLinkList::Sort()
{
    FastSort(head->next,tail);
}

void DoubleLinkList::show()
{
    std::cout << "size :" << size << std::endl;
    Node *travelPoint = head->next;
    while(travelPoint != nullptr)
    {
        Print(travelPoint->value);
        travelPoint = travelPoint->next;
    }
    std::cout << std::endl;

    travelPoint = tail;
    while(travelPoint != head)
    {
        Print(travelPoint->value);
        travelPoint = travelPoint->prev;
    }
    std::cout << std::endl;
}

void DoubleLinkList::FastSort(Node *start, Node *end)
{
    if(start == end)
        return ;
    Node * left = start;
    Node * right = end;
    ElementType temp = start->value;
    while(left != right)
    {
        while(Greater(right->value,temp) && left != right)     //right->value > temp
            right = right->prev;
        if(left != right)
        {
            left->value = right->value;
            left = left->next;
        }
        while(Greater(left->value,temp) == false && left != right)      //left->value < temp
            left = left->next;
        if(left != right)
        {
            right->value = left->value;
            right = right->prev;
        }
    }
    right->value = temp;
    if(left != start)
        FastSort(start,left->prev);
    if(left != end)
        FastSort(left->next,end);
}
